package com.study.leetcode;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

//https://leetcode-cn.com/problems/valid-parentheses/
public class ValidParentheses {
    public boolean isValid(String s) {
        //输入验证
        if (s == null || s.length() == 0) {
            return false;
        }
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> characterMap = new HashMap<>();
        //对于的开始字符映射
        characterMap.put(')', '(');
        characterMap.put('}', '{');
        characterMap.put(']', '[');
        for (int i = 0; i < s.length(); i++) {
            //如果是结束字符开始检验
            if (s.charAt(i) == ')' || s.charAt(i) == '}' || s.charAt(i) == ']') {
                //如果输入结束的括号 栈内没有元素则括号不匹配
                if (stack.empty()) {
                    return false;
                }
                Character start = characterMap.get(s.charAt(i));
                //这里第一个一定是匹配如果不匹配则括号不匹配
                if (!start.equals(stack.pop())) {
                    return false;
                }
            } else {
                //开始字符入栈
                stack.push(s.charAt(i));
            }
        }
        //正常结束栈内没有元素
        return stack.empty();
    }

}
